import java.util.Arrays;

public class TextHeap {
    public int[] elem;
    public int usedSizs;
    public TextHeap(){
        this.elem = new int[10];
    }
    // 创建大根堆
    public void creatHeap(int[] Array){
        for (int i = 0; i < Array.length; i++) {
            elem[i]= Array[i];
            usedSizs++;
        }
        // 把原始数据给到了elem 数组
        // 找到每个子树的父亲结点，再向下调整
        for (int parent = (usedSizs-1-1)/2; parent <= 0; parent++) {
            shiftDown(parent,usedSizs);
        }

    }
    // 向下调整
    private void shiftDown(int parent,int len){
        int child = parent*2+1;
        // 是不是一定有做孩子
        while (child<len){
            // 要看看是否有右孩子,防止数组越界
            if(child+1<len && elem[child]<elem[child+1]){
                child=child+1;
            }
            if(elem[parent]<elem[child]){
                int temp = elem[parent];
                elem[parent]=elem[child];
                elem[child]=temp;
            } else {
                break;
            }
            parent=child;
            child=parent*2+1;
        }
    }
    // 插入数据
    public void push(int val){
        // 1) 判断是否满了
        if(isFull()){
            elem = Arrays.copyOf(elem,2*elem.length);
        }
        // 2) 存放数据
        elem[usedSizs]=val;
        usedSizs++;
        // 3) 向下调整
        shiftUp(usedSizs-1);
    }
    public boolean isFull(){
        return usedSizs==elem.length;
    }
    public void shiftUp(int child){
        int parent = (child-1)/2;
        while (child>0){
            if(elem[child] > elem[parent]){
                int temp = elem[parent];
                elem[parent]=elem[child];
                elem[child]=temp;
                child = parent;
                parent = (child-1)/2;
            }else{
                break;
            }
        }
    }
    // 删除元素，只能删除堆顶元素
    public void poll(){
        // 1) 判断是否为空
        if(empty()){
            throw new HeapEmptyException("优先级队列是空的！");
        }
        // 2) 0下标 和 最后一个下标 交换 位置
        int temp = elem[0];
        elem[0]=elem[usedSizs-1];
        elem[usedSizs-1]=temp;
        // 3) 向下调整
        usedSizs--;
        shiftDown(0,usedSizs);
    }
    public boolean empty(){
        return usedSizs==0;
    }
    // 从大到小排序二叉树
    public void heapSort(){
        int end = usedSizs-1;
        while (end>0){
            int tmp = elem[end];
            elem[end]=elem[0];
            elem[0]=tmp;
            shiftDown(0,end);
            end--;
        }
    }
}
